class Solution {
public:
    int sqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int low = 0;
        int high = x;
        int mid = 0;
        int ans = 0;

        while (low <= high) {
            mid = low + (high - low) / 2;
            if (static_cast<long long>(mid) * mid >
                static_cast<long long>(x)) {
                high = mid - 1;
            } else {
                ans = mid;
                low = mid + 1;
            }
        }
        return ans;
    }
};
